一个网站有100亿URL存在一个黑名单中，每条URL平均有64字节。这个黑名单要怎么存？若此时随便输入一个URL，如何快速判断该URL是否在这个黑名单中。
如果不考虑细节，此题就是一个简单的查找问题。对于查找问题，使用散列表来处理往往是一种效率比较高的方案。但是100亿条URL，全部存储的话需要640G的内存空间。又因为使用了散列表这种数据结构，而散列表是会出现散列冲突的，为了避免出现过多的散列冲突，需要使用链表法来处理，这里就要存储链表指针。所以空间可能超过1000G了。
位图（BitMap)，先来考虑一个类似但更简单的问题：现在有一个非常庞大的数据，比如有1千万个整数，并且整数的范围是1到1亿之间，如何查找某个整数是否在这1千万个整数中，判断要么是true要么是false。因此可以使用一个存储状态的数组来处理，将1千万个整数作为数组下标，然后将对应的数组值设置成ture，比如整数233对应下标为233的数组设置为True，也就是array[233]=True。
这种方法就是位图法，用每一位来存放某种状态，适用于大规模数据，但是数据状态又不是很多的情况。它有一个优势就是空间不随集合元素内元素个数的增加而增加，它的存储空间计算方式是找到元素里面最大的元素（N），所占空间为：
$$
S=N/8 Byte
$$
当N为1亿时需要12MB空间，当N为10亿时，需要120MB。也就是说，位图法的所占空间随集合内最大元素的增大而增大，但是如果是数量很少而某个元素的值很大，比如数字1到1000亿，那消耗的空间不容乐观。
当N为1亿时需要12MB空间，当N为10亿时，需要120MB。也就是说，位图法的所占空间随集合内最大元素的增大而增大，但是如果是数量很少而某个元素的值很大，比如数字1到1000亿，那消耗的空间不容乐观。
出于对性能和内存占用的考虑，这里使用布隆过滤器才是最好的解决方案：布隆过滤器是对位图的一种改进。它可以判断一个元素是否在一个集合中，它的优势是只需要占用很小内存空间以及高效的查询效率。
它的本质是一个位数组，位数组就是每个元素都只占用1bit，并且每个元素只能是1或0，布隆数组除了一个位数组，还有k个哈希函数，当一个元素加入布隆过滤器中的时候，会进行如下操作：
举个例子，假设布隆过滤器有3个哈希函数：f1，f2，f3和一个位数组arr，现在要把2333插入布隆过滤器中：
当要判断一个值是否在布隆过滤器中，对元素进行三次哈希计算，得到值后判断位数组中的每个元素是否都为1，如果是则说明值在布隆过滤器中，如果存在一个值不是1，说明不在。
很明显，数组的容量即使再大也是有限的，那随着元素的增加，被置1 的位置也会越多，这就会造成一种情况：当一个不在布隆过滤器中的元素，经过同样规则的哈希计算后，得到的值在位数组中查询，有可能这些位置已经被其他元素的操作先置为1了，总结来讲就是
下面是分界线~